1. Field of the Invention
The present invention concerns methods of inserting additional information, such as a digital signature, in a digital image.
It also concerns methods of extracting this additional information.
Correlatively, the present invention concerns a device for inserting and a device for extracting additional information adapted to implement respectively the insertion methods and the extraction methods according to the invention.
2. Description of the Related Art
The present invention applies more generally to the field of watermarking digital data, and more particularly digital images.
In general terms, the watermarking of digital data can be interpreted as the insertion of a seal or signature, for example for authenticating the author or origin of a digital document.
Conventionally, such a signature must be inserted imperceptibly, that is to say in a fashion which is not detectable to the eye in the case of an image.
It must also be robust to the normal operations of digital signal processing, such as compression, for example, for fixed images, in accordance with the JPEG (Joint Photographic Expert Group) standard, filtering, digital to analogue conversion (for printing an image for example), analogue to digital conversion (for digitising a printed image for example) and geometric manipulations of the image, such as plane similarities integrating translations, rotations, changes of scale or even divisions.
The signature must also be robust to intentional attacks aimed at extracting or erasing it so as, for example, to arrogate the copyright over an image.
The majority of techniques for inserting additional information in digital data consist of choosing a set of so-called perceptually significant spatial or frequency components of the digital signal, in which the additional information can be inserted in a robust fashion notably vis-xc3xa1-vis the normal compression methods, signal processing operations, intentional attacks and also, to a certain extent, geometric transformations.
Such a technique is described for example in the European patent application EP 0 766 468 filed in the name of NEC CORPORATION.
These digital image watermarking techniques are based on a prior frequency transformation of the digital image, for example by means of a discrete cosine transformation by blocks, a choice of significant components amongst the components obtained by transformation, a modulation of the components chosen for inserting the signature and an inverse frequency transformation in order to obtain the watermarked image.
When the signature is extracted, the extraction method also uses a frequency transformation of the image to be authenticated, a choice of the significant components and a demodulation of these components in order to find the inserted signature.
There also exist techniques in which the coefficients are modified according to a predetermined rule, known to the decoder. The decoding step then consists of examining whether this predetermined rule is indeed verified or not. Such a technique is described for example in the document entitled xe2x80x9cVideo-steganography: how to secretly embed a signature in a picturexe2x80x9d by Matsui Kineo and Tamaka Kyoshi, IMA Intellectual Property Project Proceedings, Volume 1, issue 1, January 1994.
Nevertheless, when the image has undergone geometric transformations such as plane similarities, the parameters of these geometric transformations must be known a priori or estimated in a relatively precise fashion when the signature is extracted so as to re-fix the image in space.
Such a re-fixing is generally difficult to effect and requires having the original image at the decoder implementing the signature extraction method.
One means of getting around the difficulty is to use a frequency transformation which is invariant to the usual geometric transformations, such as for example the Fourier-Mellin transformation invariant to rotations and changes in scale, described in the article by J. RUANAIDH et al, xe2x80x9cRotation, scale and translation invariant spread spectrum digital image watermarkingxe2x80x9d, Signal Processing, 6, 1998.
Such a watermarking method is of limited application since it does not make it possible to use the conventional spectral decomposition methods in the domain of the digital images, such as Fourier transforms, discrete cosine transforms, either global or by blocks, or discrete wavelet transforms.
Another technique is described in international patent application WO 97/43736 in which a fixed reference is inserted invisibly in the image at the time of insertion of the signature. This reference is then detected in order to re-fix the image before extraction of the signature.
However, this method requires the insertion of additional information imperceptibly, independently of the signature itself.
In addition, this reference can be detected intentionally with statistical methods and be intentionally erased.
The aim of the present invention is in a first aspect to propose a method of inserting and extracting a signature in a digital image which makes it possible effectively to know and reverse the geometric transformations applied to a digital image.
To this end, the method of inserting additional information, such as a digital signal, in a digital image, comprises the following steps:
detecting the points of interest in said image;
selecting a subset of points of interest adapted to define a geometric reference frame in said image;
calculating, for the geometric reference frame, reference information necessary for determining the geometric transformation applied to the image for a class of predetermined geometric transformations;
coding said reference information in a reference key; and
inserting the additional information in said digital image.
Correlatively, the method of extracting additional information, such as a digital signature, inserted in a digital image, comprises the following steps:
detecting the points of interest in said image;
selecting a subset of points of interest adapted to define a geometric reference frame in said image in accordance with selection criteria identical to those used during the insertion of the additional information in the original digital image;
decoding a reference key in order to extract reference information necessary for determining the geometric transformation applied to the original digital image;
calculating the parameters of the geometric transformation applied to the original image from said subset of points of interest and the reference information extracted;
re-fixing the digital image by applying an inverse geometric transformation determined from the calculated parameters; and
extracting said additional information from the re-fixed image.
Thus the image can be effectively re-fixed in space before the inserted signature is extracted, by means of selected points of interest and reference information calculated when the signature is inserted.
The means used for re-fixing the digital image are consequently dependent on the image itself and do not make it necessary to use additional information.
Such a method is robust to intentional attacks which seek to modify or destroy the signature inserted by means of the use of a reference key, possibly encrypted.
By definition, the points of interest are local characteristics of the image which convey significant information on the content of the image. This is a case mainly of the points where the bidimensional variations in the light intensity are great, such as for example corners.
Advantageously, it is shown that these points of interest, detected for example by a detector known as a Harris detector, are relatively invariant to geometric transformations such as rotation, translation, change in scale and also change in point of view, and are consequently particularly well suited to defining a geometric reference frame which can be used for re-fixing the digital image before the signature is extracted.
In addition, such a method is robust to the conventional compression techniques used for coding the digital images. This is because the points of interest are entities which are generally preserved after compression since they represent significant information on the content of the image.
According to a preferred characteristic of the invention, the reference information necessary and sufficient for geometric transformations of plane similarity types comprises four parameters calculated from the geometric reference frame.
In this way, for a class of geometric transformations, the quantity of information which it is necessary to calculate and store in a reference key to be supplied for decoding is minimised.
The four parameters are sufficient for defining an angle, a distance and the coordinates of a point of origin of the geometric reference frame in the digital image or the coordinates of two points of the geometric reference frame in the digital image.
The quantity of information to be decoded for re-fixing the image is also minimised whilst make it possible to calculate, at the calculation step of the extraction method, the parameters of the geometric transformation, which are, for geometric transformations of plane similarity types, an angle of rotation, a homothetic transformation factor and a translational movement in two perpendicular directions of the digital image.
In order to minimise this reference information still further, the latter can in practice be limited to two parameters characterising an angle and a distance, a predetermined point of interest amongst the subset of selected points of interest being chosen as the origin of the reference frame of the modifications during the step of inserting and extracting the additional information.
This is because the techniques of inserting/extracting additional information can be classified according to the signal representation domain, spatial, frequency or spatio-frequency, in which the operations of inserting/extracting the additional information take place. The insertion proper may be effected by modulation of the amplitude of the coefficients of the representation domain considered. This modulation is always defined with respect to a reference frame and it is necessary, during the extraction step, to re-fix this signal to be coded in this reference frame, which can be referred to as the modulation or demodulation reference frame, so as to be able to extract the additional information.
The insertion can also be effected by modifying the coefficients in accordance with a pre-established rule, for example by requantising these coefficients. This modification will also be defined with respect to a modification reference frame and it will also be necessary to re-fix the signal to be decoded in this reference frame so as to extract the additional information inserted.
In the case of an insertion in the spatial domain, ie the pixel domain, it therefore suffices to define the reference frame of the modifications with respect to the geometric reference frame chosen, the most simple being to take the same. In the case of an insertion in the frequency or spatio-frequency domain, the reference frame of the modifications in the transformed domain cannot be directly linked to the geometric reference frame. On the other hand it is the transformation of the signal itself, that is to say the block cosine transform or the discrete wavelet transform, which must be defined with respect to the geometric reference frame chosen, given a reference frame of the modifications which is fixed in the transformed domain. For example, the origin of the transformation of the signal at the origin of the geometric reference frame chosen will be chosen, considering the horizontal and vertical axes as the main axes of the transformation. More generally, the reference frame of the modifications is defined with respect to the phase of the representation of the signal under consideration having as its origin the geometric reference frame chosen.
According to another preferred characteristic of the invention, the insertion method also includes a step of calculating selection information on said subset of points of interest and a step of coding said selection information in a selection key.
Correlatively, the step of selecting the extraction method includes a step of decoding a selection key in order to extract selection information for said subset of points of interest.
This arrangement makes it possible to choose the points of interest by employing certain local or global geometric constraints, storing and then decoding the selection key making it possible to find the subset of points of interest chosen.
The use of a selection key characterising the selection of points of interest further increases the robustness of the method against intentional attacks.
Preferably, the selection information comprises invariant quantities for said class of predetermined geometric transformations, the value of the invariant quantities uniquely characterising a subset of points of interest in said image.
The selection information thus constituted is sufficient for finding, from the geometric invariants, the subset of points defining the geometric reference frame in the image to be re-fixed.
There also, the selection information depends only on the image itself and is therefore difficult to attack intentionally if the selection key is not available.
In practice, the subset of points of interest comprises a triplet of points of interest and the selection information comprises an angle and a distance ratio characterising said triplet of points of interest for geometric transformations of plane similitudes.
Although in absolute terms two points of interest suffice for calculating the reference information sufficient for re-fixing the image, the use of a third point for defining the geometric reference frame makes it possible to obtain a more reliable detection of the combination of points chosen in the image from the unique value of the geometric invariants.
Alternatively, the selection information can comprise criteria of an interactive selection guided by an operator, which can thus, for each image, visually choose, for example amongst the points of interest, those which are best suited to the definition of a geometric reference frame and to a simple calculation of the reference information.
According to one embodiment of the invention, not requiring the storage and decoding of a selection key, the points of interest with the greatest magnitudes at the output of the points of interest detector are selected at the selection step.
According to another characteristic of the invention, which advantageously makes it possible to use the detected points of interest, the step of inserting additional information comprises a step of choosing perceptually significant components to be modified for the insertion of the additional information, said perceptually significant components being chosen in the vicinity of said selected points of interest.
Correlatively, the step of extracting additional information comprises a step of choosing perceptually significant components modified for the insertion of the additional information, said perceptually significant components being chosen in the vicinity of said selected points of interest.
The insertion, and following that the extraction, of the additional information can thus be effected in a localised fashion, in the vicinity of the points of interest. The latter being intrinsically robust to the techniques of digital image compression, the signature is thus inserted robustly in the digital image.
Moreover, the choice of the significant components is effected independently of any spectral transformation of the image, which makes it possible to use a local watermarking method in which the additional information is directly inserted on the spatial components of the pixel domain.
According to one advantageous characteristic of the invention, the insertion step comprises a step of spatio-frequency transformation of the digital image after the step of choosing the perceptually significant components.
Correlatively, the extraction step comprises a step of spatio-frequency transformation of the digital image after the step of choosing the perceptually significant components.
Unlike the conventional techniques for watermarking digital images, the choice of the significant components can be effected before spectral transformation of the image provided that the insertion technique is space-frequency hybrid, that is to say that the additional information is inserted on components defined both in space and in frequency, obtained for example by spatio-frequency transformations like discrete cosine transform by block or discrete wavelet transform type.
In a similar fashion, the invention also concerns in its first aspect a device for inserting additional information, such as a digital signature, in a digital image, characterised in that it has:
means of detecting the points of interest in said image;
means of selecting a subset of points of interest adapted to define a geometric reference frame in said image;
means of calculating, for the geometric reference frame, reference information necessary for determining the geometric transformation applied to the image for a class of predetermined geometric transformations;
means of coding said reference information in a reference key; and
means of inserting the additional information in said digital image.
It also concerns a device for extracting additional information, such as a digital signature, inserted in a digital image, characterised in that it has:
means of detecting the points of interest in said image;
means of selecting a subset of points of interest adapted to define a geometric reference frame in said image in accordance with selection criteria identical to those used during the insertion of the additional information in the original digital image;
means of decoding a reference key in order to extract reference information necessary for determining the geometric transformation applied to the original digital image;
means of calculating the parameters of the geometric transformation applied to the original image from said subset of points of interest and the reference information extracted;
means of re-fixing the digital image by applying an inverse geometric transformation determined from the calculated parameters; and
means of extracting said additional information in the re-fixed image.
These insertion and extraction devices have characteristics and advantages similar to those described above since they are adapted to implement the methods of inserting and extracting additional information in accordance with the invention.
According to a second aspect of the invention, it appears that the choice of perceptually significant components is a crucial aspects of these techniques of inserting and extracting a digital signal.
An analysis of the prior techniques shows that the most effective watermarking techniques, such as the method described in the document EP 0 766 468 cited above, are based on a choice amongst frequency components or space/frequency hybrid components (that is to say those located both in the image space and in the frequency domain) of significant components of greater amplitude, in the sense of the greatest local energy.
An image processing method is also described in the patent application (09/318,819) wherein a digital image is divided into blocks, and a group of pixels for determining pixels in which information should be embedded and a group of pixels for embedding are selected as pixels different from each other.
The group of pixels for determination surrounds the group of pixels for embedding.
Watermark information is embedded into a block if the density variation of the group of pixels for determination is greater than a predetermined threshold value.
The aim of the present invention in its second aspect is to propose a method of inserting and extracting a signature in a digital image which make it possible to effectively select significant components which can be used for inserting a digital signature robustly in an image and which can be found in a reliable way in the image to be decoded.
To this end, the method of inserting additional information, such as a digital signature, in a digital image, comprises in a second aspect of the invention the following steps:
detecting the points of interest in said image;
selecting a subset of points of interest;
calculating a selection information comprising invariant quantities for a class of predetermined geometric transformations, the value of the invariant quantities uniquely characterising said subset of points of interest in said image;
choosing perceptually significant components to be modified for inserting the additional information in the vicinity of said selected points of interest; and
inserting the additional information by modifying said perceptually significant components.
Correlatively, the present invention in its second aspect concerns a method of extracting additional information, such as a digital signature, inserted in a digital image, comprising the following steps:
detecting the points of interest in said image;
selecting a subset of points of interest according to a selection information comprising invariant quantities for a class of predetermined geometric transformations, the value of the invariant quantities uniquely characterising said subset of points of interest in said image;
choosing perceptually significant components modified for inserting the additional information in the vicinity of the said selected points of interest; and
extracting the additional information from said modified perceptually significant components.
The insertion, and subsequently the extraction, of the additional information can thus be performed in a localised fashion, in the vicinity of the points of interest. Since the latter are intrinsically robust to digital image compression techniques, the signature is thus inserted robustly in the digital image.
Moreover, the choice of significant components is made independently of any spectral transformation of the image, which makes it possible to use a local marking method in which the additional information is directly inserted on the spatial components of the pixel domain.
The selection information thus constituted is sufficient for finding, from the geometric invariants, the subset of points of interest selected in the image to be decoded.
The selection information depends only on the image itself and is therefore difficult to attack intentionally if the selection key is not available.
According to one advantageous characteristic of the invention, the insertion step comprises a step of spatio-frequency transformation of the digital image after the step of choosing the perceptually significant components.
Correlatively, the extraction step comprises a step of spatio-frequency transformation of the digital image after the step of choosing the perceptually significant components.
Unlike the conventional techniques of watermarking digital images, the choice of the significant components can be made before spectral transformation of the image since the insertion technique is hybrid, that is to say the additional information is inserted on components defined both in space and in frequency, obtained for example by spatio-frequency transformations like discrete block cosine transform type or discrete wavelet transform type.
In practice, the insertion step comprises a step of modifying transformed coefficients where the support of an associated basic synthesis function covers a selected point of interest.
In a similar fashion, the extraction step is performed using transformed coefficients where the support of an associated basic synthesis function covers a selected point of interest.
It is a case then of checking the actual insertion of the additional information by verifying a pre-established rule known to the decoder.
According to one advantageous characteristic, the insertion, or respectively extraction, step comprises a spatio-frequency transformation step implemented in the vicinity of the points of interest selected.
By virtue of this advantageous characteristic, the spatio-frequency decomposition of the image, necessary for inserting or extracting the signature using the spectral components, can be implemented locally in the vicinity of the points of interest rather than on the whole of the image.
In practical terms, the frequency transform can be a discrete block cosine transform of the digital image, used as standardised in the JPEG standard for the processing of fixed images or a discrete wavelet transform.
According to a preferred characteristic of the invention, the insertion method also includes a step of coding said selection information in a selection key.
Correlatively, the extraction method selection step includes a step of decoding a selection key in order to extract selection information for said subset of points of interest.
The use of a selection key characterising the selection of points of interest further reinforces the robustness of the method against intentional attacks.
In practice, the subset of points of interest comprises a triplet of points of interest and the selection information comprises an angle and a distance ratio characterising said triplet of points of interest for geometric transformations of plane similarity types.
In a similar fashion, the invention also concerns in its second aspect a device for inserting additional information, such as a digital signature, in a digital image comprising:
means of detecting the points of interest in said image;
means of selecting a subset of points of interest;
means of calculating a selection information comprising invariant quantities for a class of predetermined geometric transformations, the value of the invariant quantities uniquely characterising said subset of points interest in said image;
means of choosing perceptually significant components to be modified for the insertion of the additional information in the vicinity of said selected points of interest; and
means of inserting the additional information by modifying said perceptually significant components.
It also concerns a device for extracting additional information, such as a digital signature, inserted in a digital image comprising:
means of detecting the points of interest in said image;
means of selecting a subset of points of interest according to a selection information comprising invariant quantities for a class of predetermined geometric transformations, the value of the invariant quantities uniquely characterising said subset of points of interest in said image;
means of choosing perceptually significant components modified for inserting the additional information in the vicinity of said selected points of interest; and
means of extracting the additional information using said modified perceptually significant components.
These insertion and extraction devices have characteristics and advantages similar to those described above since they are adapted to implement the methods of inserting and extracting additional information in accordance with the second aspect of the invention.
The invention also concerns a computer, an apparatus for processing a digital signal such as a digital image, a digital printer, a digital photographic apparatus and a digital camera having means adapted to implement the insertion method and/or the extraction method according to the first or second aspect of the invention.
These appliances have advantages similar to those described for the methods of inserting and extracting additional information which they implement.
The present invention also relates to an information storage means which can be read by a computer or by a microprocessor, integrated or not into an insertion or extraction device, possibly removable, which stores a program implementing the insertion or extraction method according to the invention.
More particularly, it also relates to a computer program product comprising software code portions for implementing the insertion or extraction method according to the first or the second aspect of the invention.
Other particularities and advantages of the invention will also emerge from the following description of an embodiment of the invention.